package DataStructure.graph.shortestPath.singleSourceShortestPath;

import DataStructure.arrayANDlist.hashTable.Node4Dijkstra;
import DataStructure.arrayANDlist.arrayApply.MatrixCheck;

/**
 * @author liujun
 * @version 1.0
 * @date 2019-12-25 21:11
 * @author-Email liujunfirst@outlook.com
 * @description 狄杰斯特拉算法
 * 迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个节点到其他节点的最短路径，
 * 它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。
 * @blogURL
 */

public class Dijkstra {

    public Node4Dijkstra[] getShortestPath(int startPoint, int[][] matrix) {
        if (!MatrixCheck.judgeisSquare(matrix)) {
            return null;
        }
        int length = matrix.length;
        Node4Dijkstra[] table = new Node4Dijkstra[length];

        //initial
        for (int i = 0; i < length; i++) {
            table[i] = new Node4Dijkstra(matrix[startPoint][i]);
        }

        table[startPoint].value = 0;
        table[startPoint].visit = true;

        for (int i = 1; i < length; i++) {
            int minvalue = Integer.MAX_VALUE;
            int findpoint = 0;

            //find the min path
            for (int j = 0; j < length; j++) {
                if (!table[j].visit && table[j].value < minvalue) {
                    minvalue = table[j].value;
                    findpoint = j;
                }
            }
            //fail to find min path,then break
            if (minvalue == Integer.MAX_VALUE) {
                break;
            }
            table[findpoint].visit = true;
            table[findpoint].value = minvalue;

            //update the table
            for (int j = 0; j < length; j++) {
                if (!table[j].visit &&
                        matrix[findpoint][j] != Integer.MAX_VALUE &&
                        table[j].value > matrix[findpoint][j] + minvalue) {
                    table[j].value = matrix[findpoint][j] + minvalue;
                }
            }
        }

        return table;
    }
}
